调度感知同步数据流建模

对流应用系统进行吞吐量分析需要将周期静态顺序调度建模到数据流图中,吞吐量分析效率依赖于数据流图的规模及建模时间。为了提高吞吐量分析效率,提出基于同构同步数据流图的调度感知同步数据流模型及相应建模方法。通过利用应用模型结构特征及周期静态顺序调度,可减少模型中的任务、边和初始符号数目;可以使用已有分析方法对模型进行吞吐量分析。实验结果表明,所提建模方法优于已有方法,可有效提高吞吐量分析效率。     

云平台上基于关键路径截取的有向无环图应用调度算法

针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。     

图的色数与亏格的相对独立性

本文先证明如下定理:“对于每一个非负整数p,亏格为p 的图的色数可以是任意整数m, 2≤m≤[7+(1+48p/2)].”然后,据此定理得结论:当m≥3,要找到m—色图的充分必要条件基本上是不可能的,即使不说根本不可能。     

系统状态方程的信流图描述

本文从基本概念出发,结合两个具体电路讨论如何用信流图建立系统标准状态方程的方法。     

融合图嵌入的光滑主成分分析网络图像识别算法

主成分分析网络(principal component analysis network, PCANet)是一种简单的深度学习算法,在图像识别领域具有优秀的性能。将图嵌入思想融入PCANet,提出一种新的图像识别算法光滑主成分分析网络(Smooth-PCANet)。为了验证Smooth-PCANet算法的有效性,在人脸、手写体字符以及图片等不同数据集上构建实验,并将Smooth-PCANet与多种基于深度学习的图像识别算法作了对比。实验结果证明,Smooth-PCANet算法比PCANet获得了更高的识别性能,并且更有效地避免了过拟合,在小样本训练时具有显著优势。     

大型卫星地面站故障诊断的增强分层有向图方法

为了解决传统分层有向图模型在卫星地面站故障诊断面临的问题,提出了基于增强分层有向图模型的故障诊断方法。在建模过程中,考虑到卫星地面站故障征兆多、建模复杂,依据各设备工作状态的故障传播方式合并同类节点,以减小模型规模;同时,在模型中加入节点有效性使能函数,克服传统分层有向图模型中设备主备切换导致系统结构发生改变时需要重新建模的问题。在故障诊断推理过程中,采用反向回溯和正向推理相结合的方法减小故障源搜索空间,并基于各节点被搜索次数给出故障概率,提高诊断效率。以北斗卫星无线电测定业务地面站为例对单故障和多故障报警场景下的故障诊断方法进行了验证。结果表明,基于增强分层有向图模型的故障诊断方法可以提高故障诊断的准确率和全面性。     

动态拓扑图的卫星网络可视化方法

针对高度动态变化的卫星网络,提出一种基于动态拓扑图的可视化方法。动态拓扑图可视化的难点在于如何保持动态可视化过程中的稳定性,从而使用户容易地感知到网络中所发生的拓扑变化。根据卫星网络的动态变化特点,构建连续的动态拓扑图模型;设计一种保持布局稳定性的策略,并基于力引导思想提出一种动态拓扑图布局算法;以Iridium系统为典型实例,验证本文的可视化方法的合理性和可行性。实验表明,该方法能够以清晰的可视化图像支持用户对卫星网络动态拓扑的感知和理解。     

New results on rendezvous search on the interval

In a rendezvous search problem, two players are placed in a network and must try to meet each other in the least possible expected time. We look at rendezvous search on a discrete interval in which the players are initially placed using independent draws (usually assumed to be from the same distribution). Some optimal solutions are known if this distribution is uniform, and also for certain other special types of distribution. In this article, we present two new results. First, we characterize the complete set of solutions for the uniform case, showing that all optimal strategies must have two specific properties (namely, of being swept and strictly geodesic). Second, we relate search strategies on the interval to proper binary trees, and use this correspondence to derive a recurrence relation for solutions to the symmetric rendezvous problem for any initial distribution. This relation allows us to solve any such problem computationally by dynamic programming. Finally, some ideas for future research are discussed. © Wiley Periodicals, Inc. Naval Research Logistics 60: 454–467, 2013     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

一种新闻事件演化建模方法

为了准确地发现话题中事件间的潜在关系,提出一种新闻事件演化建模方法。该方法利用事件的时间关系、内容相似性、命名实体关联信息构建新的演化关系模型,并通过定义事件的五种演化模式,识别出演化过程中的开始、中间、结束事件,最后根据新演化模型及演化模式建立事件演化的有向无环图模型,揭示事件发展的潜在脉络结构。实验结果表明,本文方法能够有效检测事件演化,提升系统性能。